package com.zjsru.oneDay;

import java.util.ArrayList;
import java.util.List;
/**
 * 格雷码
 * 定义：若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code），
 * 另外由于最大数与最小数之间也仅一位数不同，即“首尾相连”，因此又称循环码或反射码。
 *
 * 输入：n = 2
 * 输出：[0,1,3,2]
 * 解释：
 *  * [0,1,3,2] 的二进制表示是 [00,01,11,10] 。
 *  * - 00 和 01 有一位不同
 *  * - 01 和 11 有一位不同
 *  * - 11 和 10 有一位不同
 * - 10 和 00 有一位不同
 * [0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
 * - 00 和 10 有一位不同
 * - 10 和 11 有一位不同
 * - 11 和 01 有一位不同
 * - 01 和 00 有一位不同
 *
 *
 *
 * */
public class grayCode {
    public static List<Integer> grayCode(int n) {
        List<Integer> ret = new ArrayList<Integer>();
        ret.add(0);
        for (int i = 1; i <= n; i++) {
            int m = ret.size();
            for (int j = m -1; j >= 0; j--) {
                ret.add(ret.get(j) | (1 << (i-1)));
            }
        }
        return ret;
    }
    public static void main(String[] args){
        grayCode grayCode = new grayCode();
        int n = 2;
        System.out.println(grayCode(2));
    }
}
